package oj;

//反转链表
public class Num206 {
    class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    /**
     *
     * 反转链表递归
     *
     * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
     *
     * LC 206题
     */
    public class Test_203 {
        /**以下文字说明要根据代码理解
         * 每次递归要干的事情相同
         * 以下代码是先 递 即将该链表一直拆到最后一个结点
         * 之后是 归 每次执行重复的操做
         *也有代码执行操作的步分是 递 的， 归 只起到返回的作用，就是边传递边执行
         * 这个递归是先传递后执行
         *
         * 总而言之都可以看成在归的时候执行的
         */
        public ListNode reverseList(ListNode head) {
            //判断空表或只有一个表，更重要的是这是递归的边界条件
            if(head==null||head.next==null){
                return head;//当第一次触发该代码时，返回的head就反转后的头结点
            }
            ListNode newHead=reverseList(head.next);//每次拆分该链表，直到拆到触发返回条件为止
            //此时创建指针指向反转后的结点

            head.next.next=head;//将传入的head.next结点的next指向它的前驱
            head.next=null;//将前驱结点的next指向null

            return newHead;//返回的值未改变，仍然是反转后的结点，在下一次递归时不变
        }

        //eg:求1+2+3+....+k  默认k>=0;
        //1.先传递后执行，就是 归 的时候执行
        public  int fun1(int k){
            if(k==0){
                return k;
            }
            int sum=fun1(k-1);
            sum+=k;
            return sum;
        }
        //2.在传递的时候就执行了
        public int fun2(int k){
            if(k==0){
                return k;
            }
            return k+fun2(k-1);
        }

        public void main(String[] args) {
            System.out.println(fun1(3));
            System.out.println(fun2(3));

        }
    }
//    public ListNode reverseList(ListNode head) {
//        if(head == null || head.next == null){
//            return head;
//        }
//        ListNode tmpHead = head.next;
//
//        ListNode newHead = reverseList(head.next);
//        tmpHead.next = head;
//        head.next = null;
//        return newHead;
//    }

}
